#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@File    :   Josephus_problem.py
@Time    :   2022/01/10 11:24:55
@Author  :   glx 
@Version :   1.0
@Contact :   18095542g@connect.polyu.hk
@Desc    :   Josephus problem
'''

# here put the import lib
""" 递推:f(n,m)= (f(n-1,m)+m)%n
理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了M位。 
然后逆过来，同时序列越界就取模, 可以得到这个递推式。
 """
def lastRemaining(n: int, m: int) -> int:
    f = 0
    ans = []
    for i in range(2,n+1):
        f = (f+m)%i
        ans.append(f)
    return f,ans

if __name__ == "__main__":
    _,ans =lastRemaining(100,7)
    print(ans)
